package everydayGrade.t4;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author: Siantar
 * @Date: 2023-07-28-22:48
 * @Description: 1.0
 */
public class T2050 {
    public int minimumTime(int n, int[][] relations, int[] time) {
        int[] dp = new int[n];
        Arrays.fill(dp, -1);
        List<Integer>[] prev = new List[n];
        for (int i = 0; i < n; i++) {
            prev[i] = new ArrayList<>();
        }
        for (int[] relation : relations) {
            int pre = relation[0] - 1, p = relation[1] - 1;
            prev[p].add(pre);
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            res = Math.max(res, dp(i, prev, dp, time));
        }
        return res;
    }

    public int dp(int p, List<Integer>[] prev, int[] dp, int[] time) {
        if (dp[p] != -1) {
            return dp[p];
        }
        int res = 0;
        for (int pre : prev[p]) {
            res = Math.max(res, dp(pre, prev, dp, time));
        }
        res += time[p];
        dp[p] = res;
        return dp[p];
    }
}
